4361. Солярий для Грибов (Hard)

И снова Михаил проводит свои эксперименты. В этот раз он решил заняться клонированием грибов. Для этого он подготовил n спор, которые вскоре посадит в землю и вырастит. Чтобы споры, увеличиваясь в размерах, не мешали друг другу, Михаил решил размещать их только в точках с целочисленными координатами.

Кроме того, чтобы ускорить рост, он планирует построить большую круглую лампу, которая будет согревать подрастающие грибы. Центр лампы он также собирается разместить в точке с целочисленными координатами, а её радиус сделать целым числом.

Но как выбрать подходящий радиус? Конечно, можно сделать лампу настолько большой, чтобы под неё поместился весь будущий грибной лес. Однако это займёт слишком много времени, а у Михаила его в обрез. Поэтому радиус лампы должен быть как можно меньше.

Вход. Количество спор n (0 ≤ n ≤ 3141592649625).

Выход. Выведите минимально возможный целочисленный радиус лампы, под которой смогут поместиться все n спор.

Пример входа	Пример выхода
5	1

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Разобьём множество точек с целочисленными координатами на пять частей, как показано на рисунке: одна точка находится в центре, а остальные четыре части симметричны между собой и покрывают четыре четверти круга. Если количество точек, лежащих в одной из четвертей, равно res, то общее количество точек в круге будет равно 4 * res + 1.

Вычислим значение res. Пусть радиус круга равен r. Переберём значения y от 0 до r. Тогда на прямой y = k (0 ≤ k ≤ r) внутри круга окажется точек с целочисленными координатами. Общее количество таких точек на всех уровнях y и будет значением res:

Обозначим через f(r) общее количество целочисленных точек внутри круга радиуса r. Тогда:

f(r) = 4 * + 1

Функция f монотонно возрастает. Задача заключается в том, чтобы найти минимальное значение r, для которого выполняется равенство f(r) = n. Радиус лампы r будем искать с помощью бинарного поиска.

Реализация алгоритма

Функция count возвращает количество точек с целочисленными координатами, расположенных внутри круга радиуса r.

long long count(long long r)

{

long long res = 0;

double r2 = r * r;

for (long long y = 0; y <= r; y++)

res += (long long)sqrt(r2 - y*y);

return 4 * res + 1;

}

Основная часть программы. Читаем входное значение n.

scanf("%lld",&n);

Радиус круга, который покрывает как минимум n точек, ищем с помощью бинарного поиска. Изначально предполагаем, что искомый радиус находится в диапазоне [l; r] = [0; 1000000].

l = 0; r = 1000000;

while (l < r)

{

m = (l + r ) / 2;

Если количество точек в круге радиуса m меньше n, увеличиваем левую границу интервала до m + 1 – радиуса m недостаточно для покрытия n точек. В противном случае уменьшаем правую границу.

if (count (m) < n) l = m + 1; else r = m;

}

Выводим ответ.

printf("%d\n",l);